package 剑指offer.数学;

/**
 * 输入一个整数 n，求 1~n 中这些整数里面 1 出现的次数
 *
 * 1 ~ 12 中有1、10、11、12其中1出现了5次
 */
public class 第43题1到n整数中1出现的次数 {

    /*
    怎么把 10、11、12 里面的 1 找出来？
    10 / 10 = 1
    11 % 10 = 1
    12 / 10 = 1

    怎么把 101 里面的 1 找出来？
    101 % 10 = 1
    101 / 10  = 10
    10 / 10 = 1
     */
    public static int NumberOf1Between1AndN_Solution(int n) {
        int number = 0;
        for (int i = 1; i <= n; i++) {
            number += getNum(i);
        }
        return number;
    }

    public static int getNum(int i) {
        int number = 0;
        // 如果数字里面含 1 一定与 10 的整数倍有关
        // 通过取余可以确定低位里面是否有 1
        // 然后排除低位，缩小数据，继续检查下一个低位是否有 1。
        // 如果 i 是 10 的话, 10 % 10 = 0，但是 10/10 =1,1%10=1
        while (i != 0) {
            if (i % 10 == 1) {
                number++;
            }
            i /= 10;
        }
        return number;
    }

    public static void main(String[] args) {
        System.out.println(NumberOf1Between1AndN_Solution(12));
    }
}
